[NOI2020]翻修道路 部分分题解 正解已咕

给定一张带边权的弦图，给定起点终点，求这两点之间不是割集的最短路径的长度。

部分分：所有边权为 $1$

求出任意一条最短路，如果它合法就输出它的长度，否则输出 $-1$。正确性证明：

显然最短路合法就输出一定是正确的。如果最短路不合法，我们找到它的最小的、是割集的子集。由于这是最小割集，它一定把原图分成了恰好两个连通块，而且其中每一条边都横跨了两个连通块。那么有以下几种情况：

• 这个割集的大小为 $1$，那么其中唯一的一条边就是原图的割边，起点到终点的任意一条路径都要经过它，于是无解。

• 这个割集的大小大于 $1$，且它不连通。我们随便找出其中两条不相邻的边来看，假设这两条边分别是 $xu$ 和 $vy$，它大概像这样：（图片来自 matthew99 的官方题解 PPT）

假设 $P_{xv}$ 和 $P_{uy}$ 分别是删掉割集后，$x$ 到 $v$ 和 $u$ 到 $y$ 的经过的最短路径。那么 $P_{xv}+xu+P_{uy}+vy$ 是一个长度至少为 $4$ 的环，这个环上应该有弦，但是不管怎么加弦，要么与割集两边不连通矛盾，要么与 $P_{xv}$ 和 $P_{uy}$ 是最短路径矛盾。

• 这个割集的大小大于 $1$，且它连通。和刚才相反，我们随便找出其中两条相邻的边来看。设这两条边是 $uv$ 和 $vw$，它大概像这样：

如果 $uw$ 之间没有直接连边，假设它们删掉割集后的最短路径是 $P_{uw}$。那么 $uv+vw+P_{uw}$ 是一个长度至少为 $4$ 的环，和上面类似，不管怎么加弦都要矛盾。我们只能加 $uw$ 这条弦。但是如果 $uw$ 之间有直接连边，这又和一开始我们找的是最短路矛盾。

综上所述，如果最短路是割集，一定是上面的第一种情况，输出 $-1$ 一定是正确的。部分分做法到此结束。

正解

它永远地咕咕了。